#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

/**
 * @方法: 二分查找
 * @时间复杂度: o()
 * @空间复杂度: o()
 * @评价:
*/
int getC(const vector<int>& nums, int capacity) {
    int ans = 1;
    int c = capacity;
    for (int n : nums) {
        if (c >= n) {
            c -= n;
        } else {
            ans++;
            c = capacity - n;
        }
    }
    return ans;
}

int splitArray(vector<int>& nums, int m) {
    int l = *max_element(nums.begin(), nums.end());
    int r = accumulate(nums.begin(), nums.end(), 0);
    int mid;
    while (l <= r) {
        mid = l + (r - l) / 2;
        if (getC(nums, mid) <= m) {
            r = mid - 1;
        }else{
            l = mid + 1;
        }
    }
    return l;
}

/**
 * @方法: 动态规划
 * @时间复杂度: o()
 * @空间复杂度: o()
 * @评价:
*/

int splitArray(vector<int>& nums, int m) {

    return 1;
}